package nl.rug.jvleusen.datastructurelib.set;

import java.lang.reflect.Array;
import java.util.Collection;
import java.util.Iterator;
import java.util.ListIterator;
import java.util.NoSuchElementException;
import nl.rug.jvleusen.datastructurelib.ISet;

/**
 * This is an implementation of the Doubly Linked List, it behaves as a normal
 * LinkedList but adds a {@link DoublyLinkedList#listIterator()} method that
 * allows going back as well as forward.
 *
 * @author Jeroen van Leusen
 */
public class DoublyLinkedList<E> implements ISet<E> {

    /*
     * Structure is set us so the first element of the list is header.next; you
     * can iterate through it by getting the next element each time until the
     * element == header again.
     */
    private ListNode<E> header = new ListNode<E>(null);
    private int size = 0;

    /**
     * Initialize this DoublyLinkedList
     */
    public DoublyLinkedList() {
        //Set up list
        header.previous = header;
        header.next = header.previous;
    }

    /**
     * Initializes this DoublyLinkedList and adds all elements of c to it.
     * @param c
     */
    public DoublyLinkedList(Collection<? extends E> c) {
        //Make sure list is initialized.
        this();

        //Add all elements of c.
        addAll(c);
    }

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size() == 0;
    }

    public boolean contains(Object o) {
        return indexOf(o) != -1;
    }

    public Iterator<E> iterator() {
        return listIterator();
    }

    /**
     * This will return an implementation of {@link ListIterator} for this
     * instance.
     *
     * @return A listIterator for this instance.
     */
    public ListIterator<E> listIterator() {
        return new ListItr();
    }

    /**
     * {@inheritDoc}
     */
    public ISet<E> union(ISet<E> set2) {
        DoublyLinkedList<E> result = new DoublyLinkedList(this);
        result.addAll(set2);
        return result;
    }

    /**
     * {@inheritDoc}
     */
    public ISet<E> intersection(ISet<E> set2) {
        DoublyLinkedList<E> result = new DoublyLinkedList(this);
        result.retainAll(set2);
        return result;
    }

    /**
     * {@inheritDoc}
     */
    public ISet<E> difference(ISet<E> set2) {
        DoublyLinkedList<E> result = (DoublyLinkedList<E>) union(set2);
        result.removeAll(intersection(set2));
        return result;
    }

    /**
     * {@inheritDoc}
     */
    public boolean subset(ISet<E> set2) {
        DoublyLinkedList<E> intersection = (DoublyLinkedList<E>) intersection(set2);
        //Intersection should contain all elements of set2.
        return intersection.containsAll(set2);
    }

    /**
     * 
     */
    public class ListItr implements ListIterator<E> {

        //According to specified standard implementation:
        private ListNode<E> lastReturned = header;
        private ListNode<E> next = header.next;
        private int nextIndex = 0;

        public boolean hasNext() {
            return nextIndex != size;
        }

        public E next() {
            if (nextIndex == size) {
                //No elements left.
                throw new NoSuchElementException();
            }
            lastReturned = next;
            next = next.next;
            nextIndex++;
            return lastReturned.data;
        }

        public void remove() {
            ListNode<E> lastNext = lastReturned.next;
            try {
                DoublyLinkedList.this.remove(lastReturned);
            } catch (NoSuchElementException e) {
                //Someone really has been messing with this list.
                throw new IllegalStateException();
            }

            nextIndex--;

            lastReturned = header;
        }

        /**
         * Additional method for listIterator for going back
         *
         * @return Whether there are previous items.
         */
        public boolean hasPrevious() {
            return nextIndex != 0;
        }

        /**
         * Additional method for listIterator for going back through the list.
         *
         * @return The previous item.
         * @throws NoSuchElementException If there are no previous elements.
         */
        public E previous() {
            if (nextIndex == 0) {
                throw new NoSuchElementException();
            }
            next = next.previous;
            lastReturned = next;
            nextIndex--;
            return lastReturned.data;
        }

        public int nextIndex() {
            return nextIndex;
        }

        public int previousIndex() {
            return nextIndex - 1;
        }

        public void set(E e) {
            throw new UnsupportedOperationException("You cannot set items, this is a set.");
        }

        public void add(E e) {
            lastReturned = header;
            addBefore(e, next);
            nextIndex++;
        }
    }

    public Object[] toArray() {
        Object[] result = new Object[size()];
        int i = 0;
        for (ListNode<E> ln = header.next; ln != header; ln = ln.next) {
            result[i++] = ln.data;
        }
        return result;
    }

    public <T> T[] toArray(T[] a) {
        //Create a new array with reflection is the array provided is too small
        if (a.length < size()) {
            a = (T[]) Array.newInstance(a.getClass().getComponentType(), size());
        }
        int i = 0;

        Object[] result = a; //This will make sure elements can throw a ArrayStoreException.
        for (ListNode<E> ln = header.next; ln != header; ln = ln.next) {
            result[i++] = ln.data;
        }

        return a;
    }

    public boolean add(E e) {
        return addBefore(e, header);
    }

    private boolean addBefore(E e, ListNode<E> node) {
        //No adding to a set if the element already exists!.
        if (contains(e)) {
            return false;
        }

        ListNode<E> newListNode = new ListNode<E>(e, node, node.previous);
        //Fix links.
        newListNode.previous.next = newListNode;
        newListNode.next.previous = newListNode;
        size++;
        return true;
    }

    public boolean remove(Object o) {
        //Split null off to avoid NPE's
        if (o == null) {
            for (ListNode<E> ln = header.next; ln != header; ln = ln.next) {
                if (ln.data == null) {
                    remove(ln);
                    return true;
                }
            }
        } else {
            for (ListNode<E> ln = header.next; ln != header; ln = ln.next) {
                if (o.equals(ln.data)) {
                    remove(ln);
                    return true;
                }
            }
        }
        return false;
    }

    private E remove(ListNode<E> listNode) {
        //Removing the header would be BAD.
        if (listNode == header) {
            throw new NoSuchElementException();
        }

        E result = listNode.data;
        listNode.previous.next = listNode.next;
        listNode.next.previous = listNode.previous;
        listNode.previous = null;
        listNode.next = null;
        listNode.data = null;
        size--;

        return result;
    }

    public boolean containsAll(Collection<?> c) {
        for (Object element : c) {
            if (!contains(element)) {
                //Its not contained within this list, return false;
                return false;
            }
        }
        return true;
    }

    public boolean addAll(Collection<? extends E> c) {
        boolean changed = false;
        for (E element : c) {
            if (add(element)) {
                //It was successfully added.
                changed = true;
            }
        }
        return changed;
    }

    public boolean removeAll(Collection<?> c) {
        boolean changed = false;

        //We need iterator.remove(), so we dont use the for (element:collection) method.
        Iterator<E> it = iterator();
        while (it.hasNext()) {
            if (c.contains(it.next())) {
                //Element contained in c, remove!
                it.remove();
                //We've changed the list!
                changed = true;
            }
        }

        return changed;
    }

    public boolean retainAll(Collection<?> c) {
        boolean changed = false;

        //We need iterator.remove(), so we dont use the for (element:collection) method.
        Iterator<E> it = iterator();
        while (it.hasNext()) {
            if (!c.contains(it.next())) {
                //Element not contained in c, remove!
                it.remove();
                //We've changed the list!
                changed = true;
            }
        }

        return changed;
    }

    public void clear() {
        ListNode<E> ln = header.next;
        //Prevent memory leaks by setting all references to null.
        while (ln != header) {
            ListNode<E> next = ln.next;
            ln.previous = null;
            ln.next = null;
            ln.data = null;
            ln = next;
        }
        //Reset header and size.
        header.previous = header;
        header.next = header.previous;
        size = 0;
    }

    /**
     * Returns the index of the specified element, if it is present, will return
     * -1 if its not present.
     *
     * @param o element to look for.
     * @return Index where the element specified exists, or -1 if the list does
     * not contain said element.
     */
    private int indexOf(Object o) {
        int index = 0;

        //Avoid NPE's!
        if (o == null) {
            for (ListNode<E> ln = header.next; ln != header; ln = ln.next) {
                if (ln.data == null) {
                    return index;
                }
                index++;
            }
        } else {
            for (ListNode<E> ln = header.next; ln != header; ln = ln.next) {
                if (o.equals(ln.data)) {
                    return index;
                }
                index++;
            }
        }

        return -1;
    }

    private static class ListNode<E> {

        private E data;
        private ListNode<E> next;
        private ListNode<E> previous;

        protected ListNode(E data) {
            this(data, null, null);
        }

        protected ListNode(E data, ListNode<E> next, ListNode<E> previous) {
            this.data = data;
            this.next = next;
            this.previous = previous;
        }
    }
}
